using System;
using System.Linq;
using System.Numerics;
using UnityEngine;

/// <summary>
/// <para>含有小数的大数, num为空表示无限大, num为null表示不是一个数字(NAN)</para>
/// <para>一个Number对象只能表示一个数, 不能在内部修改num数组等字段, 只能通过构造函数传入</para>
/// </summary>
[Serializable]
public class Number
{
    // 数字数组，从低位到高位存储(12345 -> [5, 4, 3, 2, 1])
    public readonly sbyte[] num;
    public readonly string stringNum;
    // 表示小数点后有多少位数(12345.6789 -> 5)
    public readonly int lend;
    // 表示小数点前有多少位数(12345.6789 -> 4)
    public readonly int leni;
    public bool isPositive;

    public static Number Zero = new Number(new sbyte[1] { 0 }, true, 0);
    public static Number One = new Number(new sbyte[1] { 1 }, true, 0);
    public static Number Inf = new Number(new sbyte[0], true, 0);
    public static Number MinusInf = new Number(new sbyte[0], false, 0);
    public static Number Nan = new Number("", true, 0, isNan: true);

    public Number()
    {
        num = new sbyte[] { 0 };
        stringNum = "0";
        lend = 0;
        leni = 1;
        isPositive = true;
    }

    /// <param name="reverse">为true表示是正序排列的数字</param>
    public Number(sbyte[] num, bool isPositive, int lend = 0, bool reverse = false, bool isNan = false)
    {
        // NAN
        if (isNan)
        {
            this.num = null;
            stringNum = "nan";
            return;
        }
        // 无穷大
        if (num.Length == 0)
        {
            this.num = new sbyte[0];
            this.isPositive = isPositive;
            stringNum = isPositive ? "inf" : "-inf";
            return;
        }
        // 零
        if (num.Count(x => x == 0) == num.Length)
        {
            this.num = new sbyte[1] { 0 };
            this.lend = 0;
            leni = 1;
            this.isPositive = true;
            stringNum = "0";
            return;
        }

        if (reverse) { num = num.Reverse().ToArray(); }
        int len = 1, start = 0;
        // 前导零不够位数
        if (lend < 0)
        {
            sbyte[] newNum = new sbyte[num.Length - lend];
            Array.Copy(num, 0, newNum, -lend, num.Length);
            num = newNum;
            lend = 0;
        }
        // 去除前导0
        for (int i = 0; i < num.Length; i++)
        {
            if (lend > i && num[i] != 0) { lend = Math.Max(lend - i, 0); start = i; break; }
        }
        // 后导0不够位数
        if (lend >= num.Length - start)
        {
            sbyte[] newNum = new sbyte[lend + start + 1];
            Array.Copy(num, 0, newNum, 0, num.Length);
            num = newNum;
        }
        // 去除后导0
        for (int i = num.Length - 1; i >= 0; i--)
        {
            if (num[i] != 0 || i <= lend + start) { len = i + 1; break; }
        }
        // 截取有效数字部分
        this.num = num.Where((x, i) => i >= start).Take(len - start).ToArray();
        // 计算字符串表示
        stringNum = string.Join("", this.num.Reverse());
        if (lend == 0)
            stringNum = (isPositive ? "" : "-") + stringNum[..(stringNum.Length - lend)];
        else
            stringNum = (isPositive ? "" : "-") + stringNum[..(stringNum.Length - lend)] + "." + stringNum[(stringNum.Length - lend)..];
        // 计算长度
        this.lend = lend;
        leni = len - start - lend;
        // 标注正负信息
        this.isPositive = isPositive;
    }

    /// <param name="reverse">为true表示是正序排列的数字</param>
    public Number(string num, bool isPositive, int lend = 0, bool reverse = false, bool isNan = false)
    {
        // NAN
        if (isNan)
        {
            this.num = null;
            stringNum = "nan";
            return;
        }
        // 无穷大
        if (num == null || num.Length == 0)
        {
            this.num = new sbyte[0];
            this.isPositive = isPositive;
            stringNum = isPositive ? "inf" : "-inf";
            return;
        }
        // 零
        if (num.All(x => x == '0'))
        {
            this.num = new sbyte[1] { 0 };
            this.lend = 0;
            leni = 1;
            this.isPositive = true;
            stringNum = "0";
            return;
        }

        if (reverse) { num = string.Concat(num.Reverse()); }
        int len = 1, start = 0;
        // 前导零不够位数
        if (lend < 0)
        {
            num = num.PadLeft(num.Length - lend, '0');
            lend = 0;
        }
        // 去除前导0
        for (int i = 0; i < num.Length; i++)
        {
            if (lend > i && num[i] != '0') { lend = Math.Max(lend - i, 0); start = i; break; }
        }
        // 后导0不够位数
        if (lend >= num.Length - start) num = num.PadRight(lend + start + 1, '0');
        // 去除后导0
        for (int i = num.Length - 1; i >= 0; i--)
        {
            if (num[i] != '0' || i < lend + start) { len = i + 1; break; }
        }
        // 截取有效数字部分
        this.num = num.Substring(start, len).Select(c => (sbyte)(c - '0')).ToArray();
        // 计算字符串表示
        stringNum = string.Join("", this.num.Reverse());
        if (lend == 0)
            stringNum = (isPositive ? "" : "-") + stringNum[..(stringNum.Length - lend)];
        else
            stringNum = (isPositive ? "" : "-") + stringNum[..(stringNum.Length - lend)] + "." + stringNum[(stringNum.Length - lend)..];
        // 计算长度
        this.lend = lend;
        leni = len - start - lend;
        // 标注正负信息
        this.isPositive = isPositive;
    }

    private static int NextPowerOfTwo(int n)
    {
        if (n == 0) return 1;
        n--; // 处理已经是 2 的幂的情况（如 16 → 16）
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n + 1;
    }

    private static Complex[] FFT(Complex[] a, bool inverse = false)
    {
        int n = a.Length;
        if (n == 1)
        {
            return new Complex[] { a[0] };
        }

        // 添0
        if ((n & (n - 1)) != 0)
        {
            n = NextPowerOfTwo(n);
            Complex[] newA = new Complex[n];
            Array.Copy(a, newA, a.Length);
            a = newA;
        }

        // 分奇偶下标
        Complex[] pe = a.Where((x, i) => (i & 1) == 0).ToArray();
        Complex[] po = a.Where((x, i) => (i & 1) == 1).ToArray();

        // 递归
        Complex[] qe = FFT(pe, inverse);
        Complex[] qo = FFT(po, inverse);

        // 参数
        double angle = 2 * Math.PI / n * (inverse ? -1 : 1);
        Complex omegaBase = new Complex(Math.Cos(angle), Math.Sin(angle));
        Complex omega = Complex.One;

        // 合并结果
        Complex[] ret = new Complex[n];
        for (int i = 0; i < n >> 1; i++)
        {
            ret[i] = qe[i] + omega * qo[i];
            ret[i + (n >> 1)] = qe[i] - omega * qo[i];
            omega *= omegaBase;
        }

        return ret;
    }

    /// <summary>
    /// 正数相加, 无论Number.isPositive是否为true, 一律按照正数运算
    /// 例: 
    /// 12345.6789  lend=5  leni=4
    ///   123.321   lend=3  leni=3
    /// --------------------------
    /// 12468.9999  lend=5  leni=4
    /// </summary>
    private static (sbyte[], int) Add(Number a, Number b)
    {
        // 最长整数长度、最长小数长度
        int maxLeni = Math.Max(a.leni, b.leni);
        int maxLend = Math.Max(a.lend, b.lend);
        // 计算最大长度 = 最大整数部分长度 + 最大小数部分长度 + 进位
        int maxLength = maxLeni + maxLend;
        if (a.leni == b.leni && a.num[^1] + b.num[^1] >= 10) maxLength++;

        // 结果
        sbyte[] retNum = new sbyte[maxLength];
        // 计算整数部分
        for (int i = 0; i < maxLeni; i++)
        {
            retNum[maxLend + i] += (i < a.leni) ? a.num[a.lend + i] : (sbyte)0;
            retNum[maxLend + i] += (i < b.leni) ? b.num[b.lend + i] : (sbyte)0;
        }

        // 计算小数部分
        for (int i = 0; i < maxLend; i++)
        {
            retNum[maxLend - i - 1] += (i < a.lend) ? a.num[a.lend - i - 1] : (sbyte)0;
            retNum[maxLend - i - 1] += (i < b.lend) ? b.num[b.lend - i - 1] : (sbyte)0;
        }

        // 进位
        for (int i = 0; i < maxLength; i++)
        {
            if (retNum[i] >= 10)
            {
                retNum[i + 1] += (sbyte)(retNum[i] / 10);
                retNum[i] %= 10;
            }
        }

        return (retNum, maxLend);
    }

    /// <summary>
    /// 正数相减, 无论Number.isPositive是否为true, 一律按照正数运算
    /// 例:
    ///  12345.6789  lend=5  leni=4
    /// -  123.321   lend=3  leni=3
    /// ---------------------------
    ///  12222.3579  lend=5  leni=4
    private static (sbyte[], int, bool) Sub(Number a, Number b)
    {
        // 比较两数绝对值大小, 判断是否够减
        bool isPos = false;
        if (a.leni > b.leni) isPos = true;
        else if (a.leni == b.leni)
        {
            for (int i = 0; i < Math.Max(a.num.Length, b.num.Length); i++)
            {
                // 被减数超界
                if ((i + 1) > a.num.Length) { break; }
                // 超界或更大
                if ((i + 1) > b.num.Length || a.num[^(i + 1)] > b.num[^(i + 1)]) { isPos = true; break; }
                else if (a.num[^(i + 1)] < b.num[^(i + 1)]) { isPos = false; break; }
                // 两数相等
                if ((i + 1) == a.num.Length && a.num.Length == b.num.Length &&
                    a.num[^(i + 1)] == b.num[^(i + 1)])
                {
                    isPos = true;
                    break;
                }
            }
        }

        // 分清楚大数和小数
        Number bigNum = isPos ? a : b;
        Number smallNum = isPos ? b : a;
        // 结果
        int maxLend = Math.Max(bigNum.lend, smallNum.lend);
        int maxLength = maxLend + Math.Max(bigNum.leni, smallNum.leni);
        sbyte[] retNum = new sbyte[maxLength];

        // 用大数减小数
        int bs = bigNum.lend - maxLend, ss = smallNum.lend - maxLend;
        for (int i = 0; i < maxLength; i++)
        {
            // 减法
            retNum[i] += bs + i >= 0 ? bigNum.num[bs + i] : (sbyte)0;
            retNum[i] -= ss + i >= 0 && ss + i < smallNum.num.Length ? smallNum.num[ss + i] : (sbyte)0;
            // 借位
            if (retNum[i] < 0) { retNum[i] += 10; retNum[i + 1]--; }
        }

        return (retNum, maxLend, isPos);
    }

    private static Number FindMid(Number l, Number r)
    {
        Number sum = l + r;
        sbyte[] retNum = new sbyte[sum.num.Length];
        retNum[0] = (sbyte)(sum.num[0] / 2);
        for (int i = 1; i < sum.num.Length; i++)
        {
            retNum[i] = (sbyte)(sum.num[i] / 2);
            retNum[i - 1] += (sum.num[i] & 1) == 1 ? (sbyte)5 : (sbyte)0;
        }
        return new Number(retNum, true, 0);
    }

    public static bool operator >=(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return false;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive == b.isPositive || a.isPositive;
            else if (a.num.Length == 0) return a.isPositive;
            else return b.isPositive;
        }

        if (a.isPositive == true && b.isPositive == false) return true;
        if (a.isPositive == false && b.isPositive == true) return false;

        if (a.leni > b.leni) return !(true ^ a.isPositive);
        else if (a.leni < b.leni) return !(false ^ a.isPositive);
        for (int i = 0; i < Math.Max(a.num.Length, b.num.Length); i++)
        {
            // 被减数超界
            if ((i + 1) > a.num.Length) { return !(false ^ a.isPositive); }
            // 超界或更大
            if ((i + 1) > b.num.Length || a.num[^(i + 1)] > b.num[^(i + 1)]) { return !(true ^ a.isPositive); }
            else if (a.num[^(i + 1)] < b.num[^(i + 1)]) { return !(false ^ a.isPositive); }
        }
        // 两数相等
        return !(true ^ a.isPositive);
    }

    public static bool operator <=(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return false;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive == b.isPositive || !a.isPositive;
            else if (a.num.Length == 0) return !a.isPositive;
            else return !b.isPositive;
        }

        if (a.isPositive == true && b.isPositive == false) return false;
        if (a.isPositive == false && b.isPositive == true) return true;

        if (a.leni > b.leni) return !(false ^ a.isPositive);
        else if (a.leni < b.leni) return!(true ^ a.isPositive);
        for (int i = 0; i < Math.Max(a.num.Length, b.num.Length); i++)
        {
            // 被减数超界
            if ((i + 1) > a.num.Length) { return !(true ^ a.isPositive); }
            // 超界或更大
            if ((i + 1) > b.num.Length || a.num[^(i + 1)] > b.num[^(i + 1)]) { return !(false ^ a.isPositive); }
            else if (a.num[^(i + 1)] < b.num[^(i + 1)]) { return !(true ^ a.isPositive); }
        }
        // 两数相等
        return !(true ^ a.isPositive);
    }

    public static bool operator >(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return false;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive != b.isPositive && a.isPositive;
            else if (a.num.Length == 0) return a.isPositive;
            else return b.isPositive;
        }

        if (a.isPositive == true && b.isPositive == false) return true;
        if (a.isPositive == false && b.isPositive == true) return false;

        if (a.leni > b.leni) return !(true ^ a.isPositive);
        else if (a.leni < b.leni) return!(false ^ a.isPositive);
        for (int i = 0; i < Math.Max(a.num.Length, b.num.Length); i++)
        {
            // 被减数超界
            if ((i + 1) > a.num.Length) { return !(false ^ a.isPositive); }
            // 超界或更大
            if ((i + 1) > b.num.Length || a.num[^(i + 1)] > b.num[^(i + 1)]) { return !(true ^ a.isPositive); }
            else if (a.num[^(i + 1)] < b.num[^(i + 1)]) { return !(false ^ a.isPositive); }
        }
        // 两数相等
        return !(false ^ a.isPositive);
    }

    public static bool operator <(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return false;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive != b.isPositive && !a.isPositive;
            else if (a.num.Length == 0) return !a.isPositive;
            else return !b.isPositive;
        }

        if (a.isPositive == true && b.isPositive == false) return false;
        if (a.isPositive == false && b.isPositive == true) return true;

        if (a.leni > b.leni) return !(false ^ a.isPositive);
        else if (a.leni < b.leni) return!(true ^ a.isPositive);
        for (int i = 0; i < Math.Max(a.num.Length, b.num.Length); i++)
        {
            // 被减数超界
            if ((i + 1) > a.num.Length) { return !(true ^ a.isPositive); }
            // 超界或更大
            if ((i + 1) > b.num.Length || a.num[^(i + 1)] > b.num[^(i + 1)]) { return !(false ^ a.isPositive); }
            else if (a.num[^(i + 1)] < b.num[^(i + 1)]) { return !(true ^ a.isPositive); }
        }
        // 两数相等
        return !(false ^ a.isPositive);
    }

    public static bool operator ==(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return false;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive == b.isPositive;
            else return false;
        }

        if (a.leni != b.leni || a.lend != b.lend) return false;
        if (a.isPositive != b.isPositive) return false;
        for (int i = 0; i < a.num.Length; i++)
        {
            if (a.num[i] != b.num[i]) return false;
        }
        return true;
    }

    public static bool operator !=(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return true;
        // 无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
                return a.isPositive != b.isPositive;
            else return true;
        }

        if (a.leni != b.leni || a.lend != b.lend) return true;
        if (a.isPositive != b.isPositive) return true;
        for (int i = 0; i < a.num.Length; i++)
        {
            if (a.num[i] != b.num[i]) return true;
        }
        return false;
    }

    public static Number operator +(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return Nan;
        // 出现无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
            {
                if (a.isPositive == b.isPositive) return a.isPositive ? Inf : MinusInf;
                else return Nan;
            }
            else if (a.num.Length == 0) return a.isPositive ? Inf : MinusInf;
            else return b.isPositive ? Inf : MinusInf;
        }

        sbyte[] retNum; int maxLend; bool isPos;
        // 计算结果
        if (a.isPositive == b.isPositive) { (retNum, maxLend) = Add(a, b); isPos = a.isPositive; }
        else { (retNum, maxLend, isPos) = Sub(a, b); isPos = !(a.isPositive ^ isPos); }

        return new Number(retNum, isPos, maxLend);
    }

    public static Number operator -(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return Nan;
        // 出现无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            if (a.num.Length == 0 && b.num.Length == 0)
            {
                if (a.isPositive != b.isPositive) return a.isPositive ? Inf : MinusInf;
                else return Nan;
            }
            else if (a.num.Length == 0) return a.isPositive ? Inf : MinusInf;
            else return b.isPositive ? Inf : MinusInf;
        }

        sbyte[] retNum; int maxLend; bool isPos;
        if (a.isPositive != b.isPositive) { (retNum, maxLend) = Add(a, b); isPos = a.isPositive; }
        else { (retNum, maxLend, isPos) = Sub(a, b); isPos = !(a.isPositive ^ isPos); }
        return new Number(retNum, isPos, maxLend);
    }

    public static Number operator *(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return Nan;
        // 出现无穷大
        if (a.num.Length == 0 || b.num.Length == 0)
        {
            return a.isPositive == b.isPositive ? Inf : MinusInf;
        }

        int n = NextPowerOfTwo(a.num.Length + b.num.Length);
        Complex[] aComplex = new Complex[n];
        for (int i = 0; i < a.num.Length; i++)
        {
            aComplex[i] = new Complex(a.num[i], 0);
        }
        Complex[] bComplex = new Complex[n];
        for (int i = 0; i < b.num.Length; i++)
        {
            bComplex[i] = new Complex(b.num[i], 0);
        }
        // 进行FFT
        Complex[] aFFT = FFT(aComplex);
        Complex[] bFFT = FFT(bComplex);
        // 对应位置相乘
        aFFT = aFFT.Select((x, i) => x * bFFT[i]).ToArray();
        // 进行IFFT
        Complex[] retComplex = FFT(aFFT, true);
        // 取整
        sbyte[] retNum = new sbyte[n];
        double[] nums = retComplex.Select(x => Math.Round(x.Real) / n).ToArray();
        // 进位
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] >= 10)
            {
                nums[i + 1] += Math.Floor(nums[i] / 10);
            }
            retNum[i] = (sbyte)(nums[i] % 10);
        }
        // 小数点
        int retlend = a.lend + b.lend;
        return new Number(retNum, !(a.isPositive ^ b.isPositive), retlend);
    }

    public static Number operator /(Number a, Number b)
    {
        // 出现NAN
        if (a.num == null || b.num == null) return Nan;
        // 出现无穷大
        if (a.num.Length == 0 || b.num.Length == 0) return Nan;
        
        // 处理除数为零
            if (b.num.Length == 1 && b.num[0] == 0)
                return new Number(new sbyte[] { }, a.isPositive, 0);

        // 处理被除数为零
        if (a.num.Length == 1 && a.num[0] == 0)
            return Zero;

        // 无视小数点信息, 直接将两个数当做整数进行运算
        Number dividend = new Number(a.num, true, 0);
        Number divisor = new Number(b.num, true, 0);
        int lend = a.lend - b.lend;

        // 小于除数, 在小端填零
        if (dividend < divisor)
        {
            sbyte[] newDividend = new sbyte[divisor.num.Length + 1];
            for (int i = newDividend.Length - dividend.num.Length; i < newDividend.Length; i++)
            {
                newDividend[i] = dividend.num[i - (newDividend.Length - dividend.num.Length)];
            }
            dividend = new Number(newDividend, true, 0);
            lend += dividend.num.Length - a.num.Length;
        }

        // 利用二分法进行计算
        sbyte[] lb = new sbyte[dividend.num.Length - divisor.num.Length];
        sbyte[] rb = new sbyte[dividend.num.Length - divisor.num.Length + 2];
        if (lb.Length == 0) lb = new sbyte[] { 0 }; else lb[^1] = 1;
        rb[^1] = 1;
        Number l = new Number(lb, true, 0);
        Number r = new Number(rb, true, 0);
        sbyte[] ret = null;

        while (l <= r)
        {
            Number mid = FindMid(l, r);
            Number tryNum = mid * divisor;
            if (tryNum <= dividend)
            {
                if (tryNum + divisor > dividend) { ret = mid.num; break; }
                else l = mid + new Number(new sbyte[] { 1 }, true, 0);
            }
            else r = mid - new Number(new sbyte[] { 1 }, true, 0);
        }

        return new Number(ret, !(a.isPositive ^ b.isPositive), lend);
    }

    public override bool Equals(object obj)
    {
        // 1. 检查是否为null
        if (obj == null)
            return this == null;

        // 2. 检查是否为同一类型
        if (GetType() != obj.GetType())
            return false;

        // 3. 比较关键字段
        return this == (Number)obj;
    }

    public override int GetHashCode()
    {
        unchecked // 允许整数溢出
        {
            int hash = 17;
            hash = hash * 23 + isPositive.GetHashCode();
            hash = hash * 23 + lend.GetHashCode();
            hash = hash * 23 + leni.GetHashCode();

            // 只计算前4位数字的哈希（平衡性能与唯一性）
            for (int i = 0; i < Math.Min(4, num.Length); i++)
            {
                hash = hash * 23 + num[i].GetHashCode();
            }

            return hash;
        }
    }
}
